\section{Conclusion}
We presented  algorithms and lower bounds 
for distributed computation of several graph problems. Our bounds are (almost) tight for problems such as computing a ST or a MST, while for other problems such as connectivity and shortest paths, there is a non-trivial gap between upper and lower bounds.  Understanding these bounds and investigating the best
 possible
 can provide insight into understanding the  complexity of distributed graph processing. 
% The theoretical framework is a step towards  understanding  the possibilities and limitations  of distributively solving graph problems. 
% In particular, the time complexity  implicitly captures the communication cost (which is usually the dominate cost in practice) and   thus  is a simple and uniform measure
 %to quantify the distributed complexity of large-scale data processing. % Our model and algorithms may be potentially useful to speed up implementation of several
%graph problems in distributed graph processing systems. 
%Our work raises several  open problems.
%For problems such as shortest paths and connectivity it will be important to establish non-trivial lower bounds and also improve our upper bounds if possible.
%In particular, obtaining a lower bound of $\Omega(n/k)$ for connectivity (that will match our current upper bound) is a key open question. \onlyLong{Improving bounds for various other problems such as spanners and densest subgraph will be interesting as well.}
%\enlargethispage{\baselineskip}
 
%While we show tight bounds for some problems (such as ST and MST), for several other problems such as shortest paths and connectivity it will be %important to establish non-trivial lower bounds. 
